Các trạng thái sau được phân biệt:

• Trạng thái tương thích là các trạng thái trong máy trạng thái không xung đột với bất kỳ giá trị đầu vào. Như vậy với các đầu vào giống nhau, cả hai trạng thái phải có chung một đầu ra và chung trạng thái kế tiếp (hoặc trạng thái kế tiếp không xác định), hoặc là không thay đổi trạng thái. Các trạng thái tương thích là dư thừa nếu chúng cùng xảy ra trong một máy trạng thái.
• Trạng thái phân biệt là các trạng thái trong máy trạng thái mà có ít nhất một chuỗi đầu vào tạo ra chuỗi đầu ra khác nhau - cho dù trạng thái bắt đầu là trạng thái nào.
• Trạng thái tương đương là các trạng thái trong một máy trạng thái, mà với mỗi chuỗi đầu vào có thể, chuỗi các kết quả giống nhau sẽ được tạo ra - cho dù trạng thái bắt đầu là trạng thái nào.